#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""

"""

class Solution:
    """
    @param: A: An integer array
    @param: B: An integer array
    @return: a double whose format is *.5 or *.0
    """
    def findMedianSortedArrays(self, A, B):
        # O(log(m+n))
        len_a = len(A)
        len_b = len(B)

        all_len = len_a + len_b
        if all_len % 2 == 1:
            return self.find_sorted_array_kth(A, B, all_len//2 + 1)
        else:
            n1 = self.find_sorted_array_kth(A, B, all_len//2)
            n2 = self.find_sorted_array_kth(A, B, all_len//2 + 1)
            return (n1 + n2) / 2

    def find_sorted_array_kth(self, A, B, k):
        # k 从 1开始, k是个数
        remain_k = k
        from_a = 0
        from_b = 0

        len_a = len(A)
        len_b = len(B)

        while from_a < len_a and from_b < len_b:
            if remain_k == 1:
                return min(A[from_a], B[from_b])


            availabe_a_n = len(A) - from_a - 1
            availabe_b_n = len(B) - from_b - 1

            # get a_take
            a_will_take = remain_k // 2 - 1
            if availabe_a_n < a_will_take:
                a_take = availabe_a_n
            else:
                a_take = a_will_take

            # get b_take
            b_will_take = remain_k - 2 - a_take     # 如果A和B都充足: a_take + b_take + 2 == k
            if availabe_b_n < b_will_take:
                b_take = availabe_b_n
            else:
                b_take = b_will_take


            # print(from_a, availabe_a_n)
            # print(from_b, availabe_b_n)
            # print(a_take, b_take)
            # print('remain_k %s' % remain_k)

            # update from_a, from_b, remain_k
            if A[from_a + a_take] == B[from_b + b_take]:
                return A[from_a + a_take]
            if A[from_a + a_take] < B[from_b + b_take]:
                from_a = from_a + a_take + 1
                remain_k = remain_k - (a_take + 1)
                continue
            else:
                from_b = from_b + b_take + 1
                remain_k = remain_k - (b_take + 1)
                continue

        if from_a == len_a:
            return B[from_b + remain_k-1]
        else:
            assert from_b == len_b
            return A[from_a + remain_k-1]

    def _findMedianSortedArrays(self, A, B):
        # O(m + n)
        left_a, right_a = 0, len(A)
        left_b, right_b = 0, len(B)

        while left_a < right_a and left_b < right_b and \
                (right_a - left_a) + (right_b - left_b) > 2:
            # 去掉一个最小值, 去掉一个最大值
            if A[left_a] <= B[left_b]:
                left_a += 1
            else:
                left_b += 1

            if A[right_a-1] > B[right_b-1]:
                right_a -= 1
            else:
                right_b -= 1

        if (right_a - left_a == 1) and (right_b - left_b == 1):
            sum = A[left_a] + B[left_b]
        elif left_a == right_a:
            mid1 = (left_b + right_b) // 2
            mid2 = (left_b + right_b - 1) // 2
            sum = B[mid1] + B[mid2]
        else:
            assert left_b == right_b
            # 计算 b
            mid1 = (left_a + right_a) // 2
            mid2 = (left_a + right_a - 1) // 2
            sum = A[mid1] + A[mid2]

        return sum / 2


def main():
    print("start main")
    s = Solution()
    # ret = s.findMedianSortedArrays([1,2,3, 4], [1,2, 3])
    # ret = s.findMedianSortedArrays([1,2,3, 4], [5, 6, 7, 8])
    # ret = s.findMedianSortedArrays([2], [])
    ret = s.findMedianSortedArrays([5,6,9,10], [0,2,3,4])
    # ret = s.findMedianSortedArrays([], [1])
    # ret = s.findMedianSortedArrays([], [1])
    print(ret)

if __name__ == "__main__":
    main()
